home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 09 / harrlst.sep next >
Text File  |  1987-08-13  |  4KB  |  159 lines
  1. /* Binary tree delete procedure
  2.  *
  3.  * Input parameter "s" points to a scan for an XOR
  4.  *   chained binary tree.
  5.  * The procedure deletes s->child from the tree,
  6.  *   and returns with s set by GoParent(s)
  7.  */
  8.  
  9. void Delete(s)
  10. struct Scan *s;
  11. {
  12.     struct Scan temp, *t;
  13.     struct Item *i, *j, *k;
  14.  
  15.     i = s->child;   /*i is the item to be deleted*/
  16.     GoParent(s);
  17.  
  18.     if (i->llink == i->rlink)          /* Case 1 */
  19.     {
  20.         /*
  21.          * adjust the pointers for s->child,
  22.          * i's parent
  23.          */
  24.         if (i->key < s->child->key)
  25.             s->child->llink = s->parent;
  26.         else
  27.             s->child->rlink = s->parent;
  28.     }
  29.  
  30.     else if (i->llink == s->child)     /* Case 2 */
  31.     {
  32.         /*
  33.          * adjust the pointers for s->child,
  34.          * i's parent
  35.          */
  36.  
  37.         if (i->key < s->child->key)
  38.             s->child->llink = i->rlink  ^ 
  39.                   s->parent ^ s->child;
  40.         else
  41.             s->child->rlink = i->rlink  ^
  42.                   s->parent ^ s->child;
  43.  
  44.         /*
  45.          * adjust the pointers for i's child
  46.          */
  47.  
  48.         j = i->rlink ^ s->child;
  49.         j->rlink ^= i ^ s->child;
  50.         j->llink ^= i ^ s->child;
  51.     }
  52.  
  53.     else if (i->rlink == s->child)     /* Case 3 */
  54.     {
  55.         /*
  56.          * adjust the pointers for s->child,
  57.          * i's parent
  58.          */
  59.         if( i->key < s->child->key )
  60.             s->child->llink = i->llink  ^
  61.                               s->parent ^
  62.                               s->child;
  63.         else
  64.             s->child->rlink = i->llink  ^
  65.                               s->parent ^
  66.                               s->child;
  67.         /*
  68.          * adjust the pointers for i's child
  69.          */
  70.  
  71.         j = i->llink ^ s->child;
  72.         j->rlink ^= i ^ s->child;
  73.         j->llink ^= i ^ s->child;
  74.     }
  75.  
  76.     else                               /* Case 4 */
  77.     {
  78.         j = i->llink ^ s->child;
  79.  
  80.         if (j->rlink == i)            /* Case 4a */
  81.     {
  82.             /*
  83.              * adjust the pointers for s->child,
  84.              * i's parent
  85.              */
  86.  
  87.             if (i->key < s->child->key)
  88.                 s->child->llink = j ^ s->parent;
  89.             else
  90.                 s->child->rlink = j ^ s->parent;
  91.  
  92.             /*
  93.              * adjust the pointers for i's children
  94.              */
  95.  
  96.             j->llink ^= i ^ s->child;
  97.             j->rlink  = i->rlink;
  98.             k = i->rlink ^ s->child;
  99.             k->llink ^= i ^ j;
  100.             k->rlink ^= i ^ j;
  101.     }
  102.  
  103.         else                          /* Case 4b */
  104.     {
  105.             /*
  106.              * locate the replacement item
  107.              */
  108.  
  109.             t = &temp;
  110.             Associate(t,s->root);
  111.             t->parent = s->child;
  112.             t->child  = i;
  113.             GoLeft(t);
  114.  
  115.             while( t->child->rlink != t->parent )
  116.                 GoRight(t);
  117.  
  118.             /*
  119.              * adjust the pointers to free t->child
  120.              */
  121.  
  122.             t->parent->rlink ^= t->child->llink ^
  123.                                   t->parent     ^
  124.                                   t->child;
  125.  
  126.             if (t->child->llink != t->parent)
  127.         {
  128.                 k = t->child->llink ^ t->parent;
  129.                 k->llink ^= t->parent ^ t->child;
  130.                 k->rlink ^= t->parent ^ t->child;
  131.         }
  132.  
  133.             /*
  134.              * adjust the pointers for s->child,
  135.              * i's parent
  136.              */
  137.  
  138.             if (i->key < s->child->key)
  139.                 s->child->llink = t->child ^ s->parent;
  140.             else
  141.                 s->child->rlink = t->child ^ s->parent;
  142.  
  143.             t->child->llink = i->llink;
  144.             t->child->rlink = i->rlink;
  145.  
  146.             /*
  147.              * adjust the pointers for i's children
  148.              */
  149.  
  150.             j->llink ^= i ^ t->child;
  151.             j->rlink ^= i ^ t->child;
  152.             k = i->rlink ^ s->child;
  153.             k->llink ^= i ^ j;
  154.             k->rlink ^= i ^ j;
  155.     }
  156.     }
  157.     DropItem(i);
  158. }
  159.